package io.tec.cloud.algorithm.c04_v20220613;

import io.tec.cloud.algorithm.AlgorithmUtil;

import java.util.Arrays;

public class T27_MergeSort_Iterative {


    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int mergeSize = 1;
        int N = arr.length - 1;
        while (mergeSize <= N) {
            int L = 0;
            while (L < N) {

                if (L + mergeSize > N) {
                    break;
                }

                int mid = L + mergeSize - 1;
                int R = mid + Math.min(mergeSize, N - mid);
                merge(arr, L, mid, R);
                L = R + 1;
            }
            mergeSize <<= 1;
        }

    }

    private static void merge(int[] arr, int l, int mid, int r) {

        int[] help = new int[r - l + 1];
        int li = l;
        int ri = mid + 1;
        int idx = 0;
        while (li <= mid && ri <= r) {
            help[idx++] = arr[li] < arr[ri] ? arr[li++] : arr[ri++];
        }

        while (li <= mid) {
            help[idx++] = arr[li++];
        }

        while (ri <= r) {
            help[idx++] = arr[ri++];
        }

        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }


    public static void main(String[] args) {
        int testTimes = 100_0000;
        int maxValue = 100;
        int maxLength = 100;
        for (int t = 0; t < testTimes; t++) {
            int[] arr = AlgorithmUtil.generateArray(maxValue, AlgorithmUtil.random(maxLength));
            int[] arr1 = AlgorithmUtil.copyArray(arr);
            int[] arr2 = AlgorithmUtil.copyArray(arr);
            mergeSort(arr1);
            Arrays.sort(arr2);
            if (!AlgorithmUtil.isEquals(arr1, arr2)) {
                AlgorithmUtil.printArray(arr);
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }
}
